#include <compiler/runtime_info.h>
#include <functional/assert.h>
#include "bipartite.h"

bipart* bipart_create()
{
    bipart* bp;
    bp = (bipart*)palloc( sizeof(bipart) );
    assert( bp != NULL );

    bp->head = NULL;
    bp->parti = NULL;
    bp->partii = NULL;
    return bp;
}

void* bipart_pop( bipart* bp )
{
    void* data = NULL;
    bipart_node* bn;
    if( bp->head != NULL )
    {
        bn = bp->head;
        data = bn->data;
        
        if( bn == bp->parti )
            bp->parti = bn->parti;
        else
            bp->partii = bn->partii;

        if( bp->parti != NULL && bp->partii != NULL )
        {
            if( bp->parti->index > bp->partii->index )
                bp->head = bp->parti;
            else
                bp->head = bp->partii;
        }
        else if( bp->parti != NULL )
            bp->head = bp->parti;
        else if( bp->partii != NULL )
            bp->head = bp->partii;
        else
            bp->head = NULL;

        pfree( bn );
    }
    return data;
}

void* bipart_popi( bipart* bp )
{
    void* data = NULL;
    bipart_node* bn, *bii;
    if( bp->parti != NULL )
    {
        bn = bp->parti;
        data = bn->data;
        bii = bp->partii;
        if( bn->parti != NULL )
        {
            while( bii != NULL )
            {
                if( bii->parti == bn )
                    break;
                bii = bii->partii;
            }
            if( bii != NULL )
            {
                if( bii->partii == NULL || bii->partii->index < bn->parti->index )
                    bii->parti = bn->parti;
                else
                    bii->parti = NULL;
            }
        }
        else if( bii != NULL )
            bii->parti = NULL;

        bp->parti = bn->parti;
        if( bn == bp->head )
        {
            if( bn->parti != NULL && (
                bp->partii == NULL || bn->parti->index > bp->partii->index ) )
                bp->head = bn->parti;
            else
                bp->head = bp->partii;
        }

        pfree( bn );
    }
    return data;
}

void* bipart_popii( bipart* bp )
{
    void* data = NULL;
    bipart_node* bn, *bi;
    if( bp->partii != NULL )
    {
        bn = bp->partii;
        data = bn->data;
        bi = bp->parti;
        if( bn->partii != NULL )
        {
            while( bi != NULL )
            {
                if( bi->partii == bn )
                    break;
                bi = bi->parti;
            }
            if( bi != NULL )
            {
                if( bi->parti == NULL || bi->parti->index < bn->partii->index )
                    bi->partii = bn->partii;
                else
                    bi->partii = NULL;
            }
        }
        else if( bi != NULL )
            bi->partii = NULL;
        
        bp->partii = bn->partii;
        if( bn == bp->head )
        {
            if( bn->partii != NULL && 
                ( bp->parti == NULL || bn->partii->index > bp->parti->index 
                ))
            {
                bp->head = bn->partii;
            }
            else
                bp->head = bp->parti;
        }
        
        pfree( bn );
    }
    return data;
}

void bipart_pushi( bipart* bp, void* data )
{
    bipart_node* bn;

    bn = (bipart_node*)palloc( sizeof(bipart_node) );
    assert( bn != NULL );

    bn->data = data;
    bn->parti = bp->parti;
    bp->parti = bn;
    if( bp->head != NULL )
    {
        bn->index = bp->head->index+1;
        if( bp->partii != NULL && (
            bn->parti == NULL || 
            bn->parti->index < bp->partii->index
            ) )
        {
            bn->partii = bp->partii;
        }
        else
            bn->partii = NULL;
        bp->head = bn;
    }
    else
    {
        bn->partii = NULL;
        bn->index = 0;
        bp->head = bn;
    }

}

void bipart_pushii( bipart* bp, void* data )
{
    bipart_node* bn;
    
    bn = (bipart_node*)palloc( sizeof(bipart_node) );
    assert( bn != NULL );
    
    bn->data = data;
    bn->partii = bp->partii;
    bp->partii = bn;
    if( bp->head != NULL )
    {
        bn->index = bp->head->index+1;
        if( bp->parti != NULL && (
            bn->partii == NULL || 
            bn->partii->index < bp->parti->index
            ) )
        {
            bn->parti = bp->parti;
        }
        else
            bn->parti = NULL;
        bp->head = bn;
    }
    else
    {
        bn->parti = NULL;
        bn->index = 0;
        bp->head = bn;
    }
}

bipart_node* bipart_top( bipart* bp )
{
    return bp->head;
}

bipart_node* bipart_topi( bipart* bp )
{
    return bp->parti;
}

bipart_node* bipart_topii( bipart* bp )
{
    return bp->partii;
}

void bipart_rmi( bipart *bp, bipart_node *bn )
{
	bipart_node *bi, *bii;
	if( bn == bp->parti )
	{
		bipart_popi( bp );
	}
	else
	{
		bi = bp->parti;
		while( bi != NULL && bi->parti != bn )
			bi = bi->parti;
		// error: no such node
		if( bi == NULL )
			return;

        bii = bp->partii;
        if( bn->parti != NULL )
        {
            while( bii != NULL )
            {
                if( bii->parti == bn )
                    break;
                bii = bii->partii;
            }
            if( bii != NULL )
            {
                if( bii->partii == NULL || bii->partii->index < bn->parti->index )
                    bii->parti = bn->parti;
                else
                    bii->parti = NULL;
            }
        }
        else if( bii != NULL )
            bii->parti = NULL;
		
		if( bi->partii == NULL )
			bi->partii = bn->partii;
		bi->parti = bn->parti;
        pfree( bn );
	}
}

void bipart_rmii( bipart *bp, bipart_node *bn )
{
	bipart_node *bi, *bii;
	if( bn == bp->partii )
	{
		bipart_popii( bp );
	}
	else
	{
		bii = bp->partii;
		while( bii != NULL && bii->partii != bn )
			bii = bii->partii;
		// error: no such node
		if( bii == NULL )
			return;
		
        bi = bp->parti;
        if( bn->partii != NULL )
        {
            while( bi != NULL )
            {
                if( bi->partii == bn )
                    break;
                bi = bi->parti;
            }
            if( bi != NULL )
            {
                if( bi->parti == NULL || bi->parti->index < bn->partii->index )
                    bi->partii = bn->partii;
                else
                    bi->partii = NULL;
            }
        }
        else if( bi != NULL )
            bi->partii = NULL;
		
		if( bii->parti == NULL )
			bii->parti = bn->parti;
		bii->partii = bn->partii;
        pfree( bn );
	}
}

void bipart_destroy( bipart* bp )
{
    bipart_node* bn, *b;
    bn = bp->parti;
    while( bn != NULL )
    {
        b = bn->parti;
        pfree( bn );
        bn = b;
    }

    bn = bp->partii;
    while( bn != NULL )
    {
        b = bn->partii;
        pfree( bn );
        bn = b;
    }
    pfree( bp );
}
